# [1, 2, 3]
# [[], ] <- Termination Condition
# Formula
# current_element: 数组中当前的元素
# subsets: 我们已经得到的 power set

# 就是把 current_element 和 subsets 中的每一个成员结合，结合后，再添加到 power set 的末尾，就能得到新的 power set 了。

# [[], [1], [2], [1, 2]] <- subsets
# 3    <- current_element idx = 2
# 3 + [] = [3]
# 3 + [1] = [1, 3]
# 3 + [2] = [2, 3]
# 3 + [1, 2] = [1, 2, 3]
# 

def power_set(array, idx = None):
  if idx is None:
    idx = len(array) - 1
  
  if idx < 0:
    return [[]]

  current_element = array[idx]
  subsets = power_set(array, idx - 1) # idx 这个位置的前一个位置，得到的 power set

  # 1. 遍历 subsets
  for i in range(len(subsets)):
    current_subset = subsets[i]
    subsets.append(current_subset + [current_element])

  return subsets

# [1, 2, 3]
def power_set_non_recurssive(array):
  subsets = [[]]

  for current_element in array:
    for i in range(len(subsets)):
      current_subset = subsets[i]
      subsets.append(current_subset + [current_element])

  return subsets


print(power_set_non_recurssive([1, 2, 3]))
